We start with a miscellaneous counting question
Consider the set of positive integers less than 1000, S={1,2,⋯,999}
How many elements are divisible by
i) 7, ii) 11, iii) 7 and 11, iv) 7 or 11, v) exactly one of 7 and 11, vi) neither 7 nor 11 ,
(i) 7999=142+75 This means there are 142 multiples 7 in S
or ∣7999]=142 multiples of 7 in S
(ii) By the same reasoning, there are ⌊11999⌋=⌊90+119⌋=90 multiples of 11 in S
iii) If n is divisible by 7 and 11 , since gcd(7,11)=1, n is divisible by 77
Thus ⌊77999⌋=⌊12+7775⌋=12 multiples of 7 and 11 in S
where we change l back to k by l=k in the second sum
Lemma If k+x are positive integers and k≤n then
(nk)+(nk−1)=(n+1k)
(Te prof of the lemma is strictly algebra, given the definition of the binomial coefficients)
(a combinatorial proof is also possible) Applying the lemma we have
(x+y)n+1=xn+1+k=1∑n(n+1k)xn+1−kyk+yk+1=k=0∑n+1(n+1k)xn+1−kyk and P(n+1)
is tue.
Thus the Binomial Theorem is proved by PMI
Note The lemma is the "Theory" behind Pascal's triangle that quickly gives the binomial coefficients
Starting at the top with a single 1, in what we call now 0 , corresponding to x=0, we build the sows 1,2,3,⋯ that correspond to x=1,33,⋯, using the lemma.
Exercise 1 Find the coefficient of x3y4 in the expansion of (3x−4y)10
Solution Note in the binomial theorem, the powers of the variables add up to the exponent of the binomial 3+4=7 so there is no term with, x3y4 in it ∴ It's coefficient is zero!
Exercise 2 Consider (x+x1)10
What is the constant term in it's expansion
(the term with no x's in it)
(x+x1)10=k=0∑10(10k)x10−k(x1)k
Need x's to cancel. If we take k=5 we have
(105)x10−5(x1)5=(105)x5⋅x−5=(105)∴ The constant term is (105)=5⋅4⋅3⋅2⋅1102⋅9⋅8⋅7⋅62=9×7×4=252
Some notes on the Binomial Theorem
(x+y)n=k=0∑n(nk)xn−kyk,n⩾0,n∈Z
The coefficients (nk) = number of ways to pick k from n = number of subsets of size k in a set with n elements
This leads to some interesting results about sets
We can conclude ∣P(S)∣=2∣S∣ since
(1+1)n=2n=k=0∑n(nk)= total number of subsets of S (including ∅,k=0,S,k=n)
Also (1−1)n=0n=0=k=0∑n(−1)k(nk)=k even∑(nk)−k odd∑(nk)
∴ The total number of subsets of S with even number of element = total number of subsets of S with odd number of elements
Back to counting problems
So far we have discussed permutation and combinations of distinguishable objects
We now consider permutation and combinations of indistinguishable objects
We are given a list of different types of object from which we may select repeatedly from any or all of the types
Permutations with Repetition
Suppose we have a set with n elements. Recall that the number of ways to permute r of these elements is
P(n,r)=n(n−1)⋯(n−r+1)=(n−r)!n!
This is the number of different ways to take r objects out of n, where order counts
Permutation with Repetition or Permutation with replacement is the number of ways to "indicate" r objects out of n where order count
Think of it as "catch and release"
We have n ways to pick the first object, which we record on a list, and then put back into the pool of eligible choices, and then we still have n choices for the second objet, and so on
Thus
numberr-permutations with repetition =nr
Example How many strings of length n can be made from the english alphabet?
Answer:26x
The equivalent type of formulation to "catch and release" for repetition pwblems is to assume that the r different objects being chosen from are n different types of objects with enough of each type to satisfy the conditions imposed
Combinations with Repetition
Consider the "donut" problem
We go to a donut shop to buy 6 donuts. There are 9 types of donuts to choose from
Assuming there are at least 6 of each type,
how many different ways cen we fill the order?
Since the order in which we pick the donuts does not matter to the finial outcome we can picture the situation as follows
Suppose we take out box has nine compartments, one for each type of donuts
This means there are 8=9−1 internal dividers
We now put the 6 donuts in a line inside the box, so that we have a now of 8+6=14 objects, donuts is one type and dividers is the other type
Let a bar, ∣, represent a divider and a star, ∗, represent a donut
A choice of donuts then is represented by a string of stars and bars,
Forexample
{∣∣∗∗∣∗∣∗∣∣∗∗∣∣}
represents the following choice
Type
1
2
3
4
5
6
7
8
9
Number of that type
0
0
2
1
1
0
2
0
0
Equivalently a choice of donuts is represented by a bit sting of length 14=(9−1)+6 with 6 zeros in it
There are (146) bit strings of length 14 with exactly 6 zeros in it
Theorem The number of ways to choose r object from n different types of objects is
(n−1+rr)
Example
How many solutions are there to x1+x2+x3=11 where x1,x2,x3 non-negative integers?
This is the number of ways to select 11 objects from 3 types of objects, types x1,x2,x3.
That is (3−1+1111)=(1311)=(132)=2⋅113,12=78
Example 2 How many solutions are there to x1+x2+x3=11 if x1,x2,x3 are nonnegative integers and x1,x2⩾1,x3⩾2 ?
We fist pick
1 of type x1
1 of type x2
2 of type x3
then we require that
x1+x2+x3=7 for our remaining solution
and x1,x2,x3⩾0,
This can be done in
(3−1+77)=(97)=(92)=2.19⋅8=36 ways
Permutations with Indistinguishable Objects
Let us consider the number of different strings that can he made from the letters of the word
SUCCESS
There are 4 different letters to choose from
S→3 of themU→1 of themC→2 of themE→1 of them
Exercise How many solutions are there to x1+x2+x3=11 where x1,x2⩾0 and 0≤x3≤2 ?
Solution 3 cases to consider
Case i)x3=0, have x1+x2=11
number of solutions (2−1+1111)=(1211)=12
Case ii)x3=1, have x1+x2=10
number of solutions (2−1+1010)=(1110)=11
case iii)x3=2,x1+x2=9
number of sins (2−1+99)=(109)=10
∴ Total number of solutions is 10+11+12=33
We have a total of 7 letters to permute and this can be done in 7! ways. However, there are 3 copies of the letter S that are indistinguishable from each other
There one 3!=6 ways to permute 3 objects and so each specific rearrangement of SUCCESS is got in 3! ways
To see this think of the S's as labelled S1UCCES2S3
Then the rearrangement S2UCCES1S3 is the same word as are
Also, each one of these rearrangements have 2! duplications to account for the 2 letter C's
eg SUC1C2ES5 and SUC2C1ESS are permutations of the letters that give us the same word,
Thus there are 3!2!7!=3×2×12×17×6×5×4×3×2×1=420 different 7 letter words obtainable from the letters in SUCCESS
Theorem Let n objects of k different types, where there are ni of type i,i=1,⋯,k(n=i=1∑kni), be permuted. Then there are
n1!n2!⋯nk!n! different results
Example Consider the word AARDVARK.
How many different 8 letter words can be made from its letters?
How many different 8 letter words can be made from its letters if the 3 A's must occur consecutively?
Solution
1) We have ADRVK→3→1→2→1→1 number of ways =3!1!2!1!1!8!=3⋅2⋅1⋅2⋅18⋅7⋅6⋅5⋅4⋅3⋅2⋅1=3360 ways
If we have all 3 A's consecutive then we must permute the 6 letters
AAA→1D→1R→2V→1K→1 number of ways =2!6!=6.5.4.3=360 ways.
Distributing objects into boxes
Suppose we have n different objects (distinguishable) that we wish to put into k distinguishable boxes such that ni objects go into box.
We will count the number of ways to do this by showing a 1−1 correspondence to the permutation of n objects with k types of indistinguishable objects, each with ni objects, i=1,⋯,k.
List the object 1,2,⋯,n. List the boxes, B1,B2,⋯,BR Assign to each number l,1≤l≤n, the letter of the box it goes into to get a sequence of letters Bi1Bi2⋯Bin← some of these can be the same letter
Every assignment of objects to boxes thus corresponds to one and only one permutation of n objects of k different types with ni of each type, i=1,⋯,k.
Since two sets have the same cardinality if there is a 1−1 correspondence between them, we have
Theorem The number of ways to distribute n distinguishable objects into k distinguishable boxes so that ni are placed in box i,i=1,⋯,k, is
n1!n2!⋯nk!n!
Note If can be argued, as well, that we have (nn1) ways to put n1, items in box 1, then (n−n1n2) ways to put n2 items in box 2, then (n−n1−n2n3) ways to put n, items in box 3, ⋯, finally (n−n1−n2−⋯−nk−1nk)=(nknk)=1 ways to put nk items in box k(n=n1+⋯+nk) and thus
How many ways can 5 cards be dealt to 5 players from a standard card deck?
Solution There are 6 boxes, 5 get 5 cards (dealt cards) and 1 box gets 52−5×5=52−25=27 cards (undealt cards)
number of way =(5!)527!52!= a really big number =2.976866584×1029
How many different bridge deals are there?
Solution In bridge, the 52 cards are dealt equally to 4 hands, 13 in each, so
number of ways =(13!)452!≈5.4×1028
How many bridge deals have all cards from one suit in one player's
hand?
Solution First pick a suit. This can be done in (41)=4 ways
Now take all of those cards and put them in one hand
Now deal the other 39 cards to 3 hands in
(13!)339! ways.
thus the total number of ways is
4⋅(13!)339!
Note If we take the ratio of the answers to 3 and 2, We get the probability that bridge hand will come up with one player getting all 3 cards in his hand from one suit
Probability =4⋅(13!)339!×52!(13!)4=52!4×39!×13!=158,753,389,9001§§6.4P443#1−9,126,5P454#1−9,14−16,31−37
APPENDIX 1
Recall the general definition tor the binomial coefficients that was valid for any real number in the top spot
Let α∈R, then
(αk)=k!α(α−1)⋯(α−k+1).
Generalized Binomial Theorem
Let x∈R,∣x∣<1. Let α∈R. Then
(1+x)α=k=0∑+∞(αk)xk
The proof of this result is beyond the scope of this course
We give a few examples of the first few terms of some standard expansions